POI2014 Salad Bar

POI2014 Salad Bar

题目大意：

有一个长度为$n$的字符串，每一位只会是$p$或$j$。你需要取出一个子串$S$（从左到右或从右到左一个一个取出），使得不管是从左到右还是从右往左取，都保证每时每刻已取出的$p$的个数不小于$j$的个数。你需要最大化$|S|$。

题解：

首先很容易想到把每一个$p$看做$1$，把每一个$j$看做$-1$，之后通过前缀和（$sum$）来判断是否满足条件。

如果一个子串$[L,R]$是合法的，那么必然满足以下条件:

$$\forall k \in [L+1,R] ,sum_i \le sum_k \le sum_j$$

反之，只要满足了上述条件，这个子串一定合法。

于是，我们不难想到，枚举一个每一个$L$，对于每一个$L$，向后找$R$。

对于一个$L$， 找$L$右边第一个$sum$比$i$小的下标$k$。

那么显然，$k$以及$k$右边的点，都无法做$i$的右端点。

因而只能在区间$[L+1,k-1]$找右端点。

因为要使$sum_L \le sum_x \le sum_R$，显然区间中$sum$最大的哪一个即为右端点。（若最大有多个，取最右边的那个。）

这个可以用反证法：

假设我们不以最大的为右端点。

那么有两种情况：

1. 最大的点在你取的点的左边，那么这样最大的点在$[L+1，R]$之间，但是$sum$值却比$R$ 大，显然是不合法的。
2. 最大的点在你取的点的右边。那么我们取最大的点一定可以满足，并且还比当前点更优，因而还不如取最大的那个。

综上所述，我们得到了一种复杂度为$O(nlog n)$的算法。

首先可以$O(n)$ 预处理出每一个左端点的右端点存在的可能区间。

之后对于每一个左端点，我们在区间查询最大值即可。（这个可以用线段树等数据结构来写，单次查询为$O(logn)$）。

但实际上还有一种O(n)的写法：

不妨把问题具象化：

把前缀和看做是高度，由于每一次更改的值绝对值为$1$ ，因而一个个$sum$连成了一幅连续的折线图。

我们把向上凸起的称为山峰，向下凹的称为山谷。

那么对于每一个点，我们要找的实际上是，往右延伸时，在不出现比当前点高度矮的山谷的前提下，最高的山峰的位置。

这个可以用$dp$来写。

1. 若$str_i=p$ ，那么我们有 $peak_i= \begin{cases} { peak_{ i+1} } & { (sum _{peak_{i+1}}>sum_{peak _{nxt_{i} } }) } \\ {peak_{nxt_i} }&{ (sum_{peak_{i+1}} \le sum_{peak_{nxt_{i} } }) } \end{cases}$
2. 若$str_i=j$ ，那么我们有$peak\ _i = i$

其中$nxt_i$表示，下一个出现的与当前点高度相同的点的位置。

我们可以$O(n)$预处理出$nxt$数组，又可以$O(n)$实现$dp$值的转移。

综上题目即可解。

Code:

这里只给出O(n)的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000002;
char str[N];
int n,mi,sum[N];
int nxt[N];//下一个出现的与当前点高度相同的点的位置
int vis[N<<1];
int peak[N];
int main(){
	scanf("%d %s",&n,str+1);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+(str[i]=='p'?1:-1);
	memset(vis,-1,sizeof(vis));
	for(int i=n;i>=0;i--){
		sum[i]=sum[i]+N;
		nxt[i]=vis[sum[i]];
		vis[sum[i]]=i;
	}
	int cpeak,ans=0;
	peak[n]=cpeak=n;
	for(int i=n;i>=1;i--){
		if(str[i]=='p'){
			if(~nxt[i-1]&&sum[peak[nxt[i-1]]]>=sum[cpeak])peak[i-1]=cpeak=peak[nxt[i-1]];
			else peak[i-1]=cpeak;
			ans=max(ans,cpeak-i+1);
		}
		else peak[i-1]=cpeak=i-1;
	}
	printf("%d\n",ans);
	return 0;
}
/**************************************************************
    User: YummyJay
    Language: C++
    Result: 正确
    Time:24 ms
    Memory:22204 kb
****************************************************************/